// https://leetcode.cn/problems/next-greater-element-i/
// Created by ade on 2022/8/8.
// 输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
//输出：[-1,3,-1]
//解释：nums1 中每个值的下一个更大元素如下所述：
//- 4 ，用加粗斜体标识，nums2 = [1,3,4,2,6,5]。不存在下一个更大元素，所以答案是 -1 。
//- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
//- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>

using namespace std;

class Solution {
public:
    // 直接遍历，找出每个数后面第一个大于自己的数，
    vector<int> nextGreaterElement1(vector<int> &nums1, vector<int> &nums2) {
        int len = nums2.size();
        if (len <= 1) return {-1};
        unordered_map<int, int> um = {};
        int i = 0;
        for (; i < len - 1; i++) {
            um[nums2[i]] = -1;
            for (int j = i + 1; j < len; j++) {
                if (nums2[j] > nums2[i]) {
                    um[nums2[i]] = nums2[j];
                    break;
                }
            }
        }
        um[nums2[i]] = -1;
        vector<int> res = {};
        for (auto i : nums1) {
            res.push_back(um[i]);
        }
        return res;
    }

    // 单调栈
    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2) {
        vector<int> st = {};
        unordered_map<int,int>m = {};
        for(int i = nums2.size() - 1; i >= 0;i--){
            while(!st.empty() && nums2[i] > st.back()) st.pop_back();
            m[nums2[i]] = -1;
            if(!st.empty()) m[nums2[i]] = st.back();
            st.push_back(nums2[i]);
        }
        vector<int> res(nums1.size());
        for(int i =0 ;i < nums1.size();i++) res[i] = m[nums1[i]];
        return res;
    }
};

int main() {
    vector<int> nums1 = {4, 1, 2};
    vector<int> nums2 = {1, 3, 4, 2};
    Solution so;
    auto a = so.nextGreaterElement(nums1, nums2);
    for (auto i : a) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}